import heapq
import random
from bisect import bisect_left, bisect_right
from collections import deque
from functools import cache, reduce
from itertools import count, accumulate
from math import inf, gcd, sqrt
from operator import xor
from typing import *
from .data_struct import *


def solution_1672(accounts: List[List[int]]) -> int:
    max_account = 0
    for account in accounts:
        one_total = 0
        for bank in account:
            one_total = one_total + bank
        if one_total > max_account:
            max_account = one_total
    return max_account


def solution_1599(customers: List[int], boardingCost: int, runningCost: int) -> int:
    profit = []
    waiting = customers[0]
    turn = 0
    while True:
        board = waiting if waiting < 4 else 4
        old = 0 if turn == 0 else profit[turn - 1]
        profit.append(old + board * boardingCost - runningCost)
        turn += 1
        if turn >= len(customers):
            waiting = waiting - board
        else:
            waiting = waiting - board + customers[turn]
        if waiting == 0 and turn >= len(customers):
            final_profit = max(max(profit), 0)
            if final_profit == 0:
                return -1
            else:
                return profit.index(final_profit) + 1


def solution_1944(heights: List[int]) -> List[int]:
    stack = []
    res = []
    for height in reversed(heights):
        count = 0
        while len(stack) != 0:
            p = stack[-1]
            if p < height:
                stack.pop()
                count += 1
            else:
                stack.append(height)
                break
        if len(stack) == 0:
            stack.append(height)
            res.append(count)
            continue
        else:
            res.append(count + 1)
    return res[::-1]


def solution_1686(aliceValues: List[int], bobValues: List[int]) -> int:
    heap = []
    for i in range(len(aliceValues)):
        heapq.heappush(heap, (-(aliceValues[i] + bobValues[i]), i))
    turn = True
    a_value = 0
    b_value = 0
    while len(heap) > 0:
        _, index = heapq.heappop(heap)
        if turn:
            a_value += aliceValues[index]
        else:
            b_value += bobValues[index]
        turn = not turn
    if a_value == b_value:
        return 0
    elif a_value > b_value:
        return 1
    else:
        return -1


def solution_1686_2(aliceValues: List[int], bobValues: List[int]) -> int:
    # 建立a[i],b[i]的数组,以他们的和排序
    pair = sorted(zip(aliceValues, bobValues), key=lambda p: -p[0] - p[1])
    # alice拿走下标为偶数的数，并加aliceValue
    # bob拿走下标为奇数的数，并加bobValue
    # diff为alice - bob
    diff = sum(x if i % 2 == 0 else -y for i, (x, y) in enumerate(pair))
    return (diff > 0) - (diff < 0)


def solution_1690(stones: List[int]) -> int:
    s = [0]
    for i in range(1, len(stones) + 1):
        s.append(s[i - 1] + stones[i - 1])
    # dfs(i,j)表示问题当前石子为[i,j],最大化自己的得分
    # dp 保存子问题dfs(i,j)
    # 循环不变量 dfs(i,j) = max(s[j + 1] - s[i + 1] - dfs(i + 1, j), s[j] - s[i] - dfs(i, j - 1))
    dp = [[-1] * len(stones) for _ in range(len(stones))]

    def dfs(i, j):
        if i == j:
            return 0
        if dp[i][j] != -1:
            return dp[i][j]
        dp[i][j] = max(s[j + 1] - s[i + 1] - dfs(i + 1, j), s[j] - s[i] - dfs(i, j - 1))
        return dp[i][j]

    return dfs(0, len(stones) - 1)


def solution_1690_2(stones: List[int]) -> int:
    # 转递推
    s = [0]
    for i in range(1, len(stones) + 1):
        s.append(s[i - 1] + stones[i - 1])
    # dfs(i,j)表示问题当前石子为[i,j],最大化自己的得分
    # dp 保存子问题dfs(i,j)
    # 循环不变量 dfs(i,j) = max(s[j + 1] - s[i + 1] - dfs(i + 1, j), s[j] - s[i] - dfs(i, j - 1))
    dp = [[-1] * len(stones) for _ in range(len(stones))]
    for i in range(len(stones) - 2, -1, -1):
        for j in range(1, len(stones)):
            if i == j:
                dp[i][j] = 0
            else:
                dp[i][j] = max(s[j + 1] - s[i + 1] - dp[i + 1][j], s[j] - s[i] - dp[i][j - 1])
    return dp[0][-1]


def solution_1696(nums: List[int], k: int) -> int:
    """
    超时
    """
    n = len(nums)
    dp = [-10 ** 9] * n
    dp[n - 1] = nums[n - 1]

    def dfs(i):
        if dp[i] != -10 ** 9:
            return dp[i]
        res = -10 ** 9
        for j in range(1, k + 1):
            if i + j >= n:
                continue
            res = max(res, dfs(i + j))
        dp[i] = res + nums[i]
        return dp[i]

    return dfs(0)


def solution_1696_2(nums: List[int], k: int) -> int:
    """
    单调队列
    """
    n = len(nums)
    f = [0] * n
    q = deque([0])  # 双端队列
    f[0] = nums[0]
    for i in range(1, n):
        # 移出队列首元素，保证队列中所有元素都在k步内能到达i
        # 至多需要移除1位，因为i移动步长为1，每次移动都会检查是否需要移除队首
        if q[0] < i - k:
            q.popleft()
        # 维护的队列保证f[q[0]]为整个窗口中的最大值
        # 从窗口中到达i的过程中，一定是f[q[0]]到f[i]使得f[i]最大
        f[i] = f[q[0]] + nums[i]
        # 维护单调递减的性质
        while q and f[i] > f[q[-1]]:
            q.pop()
        q.append(i)
    return f[-1]


def solution_1976(n: int, roads: List[List[int]]) -> int:
    """
    # Dijkstra + dp
    # f[i]表示节点0到节点i的最短路个数
    # dis[x]+g[x][y] < dis[y] -> f[y]=f[x] 0到y的最短路更新了
    # dis[x]+g[x][y] = dis[y] -> f[y]=f[y]+f[x] 0到y的最短路不变,但是多了一种走法
    """
    # 朴素 Dijkstra（适用于稠密图）
    mod_num = 10 ** 9 + 7
    g = [[inf for _ in range(n)] for _ in range(n)]
    for x, y, d in roads:
        g[x][y] = d
        g[y][x] = d
    dist = [inf] * n
    dist[0] = 0
    f = [0] * n
    f[0] = 1
    done = [False] * n
    while True:
        x = -1
        for i, ok in enumerate(done):
            if not ok and (x < 0 or dist[i] < dist[x]):
                x = i  # 找当前最短
        if x == n - 1:  # d[n-1]已经是最短的了,且没有一样短的
            return f[n - 1]
        done[x] = True  # 选择x
        dx = dist[x]
        for y, d in enumerate(g[x]):
            new_dis = dx + d
            if new_dis < dist[y]:
                dist[y] = new_dis
                f[y] = f[x]
            elif new_dis == dist[y]:
                f[y] = (f[y] + f[x]) % mod_num


def solution_1976_2(n: int, roads: List[List[int]]) -> int:
    # 堆优化 Dijkstra（适用于稀疏图）
    mod_num = 10 ** 9 + 7
    g = [[inf for _ in range(n)] for _ in range(n)]
    for x, y, d in roads:
        g[x][y] = d
        g[y][x] = d
    dist = [inf] * n
    dist[0] = 0
    f = [0] * n
    f[0] = 1
    h = [(dist[0], 0)]  # 注意元组大小比较顺序
    while True:
        dx, x = heapq.heappop(h)
        if x == n - 1:
            return f[n - 1]
        if dx > dist[x]:
            continue
        for y, d in enumerate(g[x]):
            new_dis = dx + d
            if new_dis < dist[y]:
                dist[y] = new_dis
                heapq.heappush(h, (new_dis, y))
                f[y] = f[x]
            elif new_dis == dist[y]:
                f[y] = (f[y] + f[x]) % mod_num


def solution_1976_3(n: int, roads: List[List[int]]) -> int:
    # 堆优化 Dijkstra（适用于稀疏图）
    mod_num = 10 ** 9 + 7
    g = [[] for _ in range(n)]
    for x, y, d in roads:
        g[x].append((y, d))
        g[y].append((x, d))
    dist = [inf] * n
    dist[0] = 0
    f = [0] * n
    f[0] = 1
    h = [(dist[0], 0)]  # 注意元组大小比较顺序
    while True:
        dx, x = heapq.heappop(h)
        if x == n - 1:
            return f[n - 1]
        if dx > dist[x]:
            continue
        for y, d in g[x]:
            new_dis = dx + d
            if new_dis < dist[y]:
                dist[y] = new_dis
                heapq.heappush(h, (new_dis, y))
                f[y] = f[x]
            elif new_dis == dist[y]:
                f[y] = (f[y] + f[x]) % mod_num


def solution_1793(nums: List[int], k: int) -> int:
    # 双指针
    p, q = k, k
    n = len(nums)
    m = nums[k]
    ans = m
    while p > -1 and q < n:
        cur = (q - p + 1) * m
        ans = max(cur, ans)
        if p == 0 and q < n - 1:
            q += 1
            m = min(m, nums[q])
        elif q == n - 1 and p > 0:
            p -= 1
            m = min(m, nums[p])
        elif p == 0 and q == n - 1:
            break
        elif nums[p - 1] < nums[q + 1]:
            q += 1
            m = min(m, nums[q])
        else:
            p -= 1
            m = min(m, nums[p])

    return ans


def solution_1793_2(nums: List[int], k: int) -> int:
    # 双指针优化
    n = len(nums)
    ans = min_h = nums[k]
    i = j = k
    # 至多走n-1次
    for _ in range(n - 1):
        # 右边没法走了或者左边比右边大
        if j == n - 1 or i and nums[i - 1] > nums[j + 1]:
            i -= 1
            min_h = min(min_h, nums[i])
        else:
            j += 1
            min_h = min(min_h, nums[j])
        ans = max(ans, min_h * (j - i + 1))
    return ans


def solution_1793_3(nums: List[int], k: int) -> int:
    # 单调栈
    n = len(nums)
    left = [-1] * n
    st = []
    for i, x in enumerate(nums):
        # 找左侧最近的比x小的坐标
        while st and x <= nums[st[-1]]:
            st.pop()
        if st:
            left[i] = st[-1]
        st.append(i)
    right = [n] * n
    st.clear()
    for i in range(n - 1, -1, -1):
        x = nums[i]
        while st and x <= nums[st[-1]]:
            st.pop()
        if st:
            right[i] = st[-1]
        st.append(i)
    ans = 0
    for h, l, r in zip(nums, left, right):
        if l < k < r:
            ans = max(ans, h * (r - l - 1))
    return ans


def solution_1969(p: int) -> int:
    """
    结论：将[1,2^p-1]分为两部分[1,2^(p-1)-1][2^(p-1),2^p-1]
    1与2^p-2配对，两个数所有1的位置不同
    2与2^p-3配对，两个数所有1的位置不同
    ...
    每个配对都使得转换后成为11...10 和 00...01，这种形式乘积最小
    证明参考
    https://leetcode.cn/problems/minimum-non-zero-product-of-the-array-elements/solutions/936621/tan-xin-ji-qi-shu-xue-zheng-ming-by-endl-uumv/

    故最小乘积为 (2^p-1)*[(2^p-2)^(2^(p-1)-1)]
    快速幂
    """
    mod_factor = 10 ** 9 + 7
    a = (1 << p) - 1
    b = (1 << (p - 1)) - 1
    c = a - 1
    ans = 1
    while b > 0:
        if b & 1:
            ans *= c % mod_factor
        c *= c % mod_factor
        b >>= 1
    return ans * a % mod_factor


def solution_1997(nextVisit: List[int]) -> int:
    mod_factor = 10 ** 9 + 7
    n = len(nextVisit)
    # f[i]表示从n[i]到i所需要的天数
    f = [0] * n
    f[0] = 0
    s = [0] * (n + 1)
    s[1] = 0
    for i in range(1, n):
        cur = nextVisit[i]
        days = s[i] - s[cur] + 2 * (i - cur)
        f[i] = days
        s[i + 1] = (s[i] + days) % mod_factor
    return (s[n - 1] + 2 * (n - 1)) % mod_factor


def solution_1997_2(nextVisit: List[int]) -> int:
    s = [0] * len(nextVisit)
    # f[i] 表示 i-> n[j] -> ... -> i
    # 因此比解1少去了2 * (i - cur)
    # 都算在f中了
    # f[i] = 2+s[i]-s[j]
    # s[i+1] = s[i]+f[i]
    # s[i+1] = s[i]*2 - s[j]+2
    for i, j in enumerate(nextVisit[:-1]):
        s[i + 1] = (s[i] * 2 - s[j] + 2) % (10 ** 9 + 7)
    return s[-1]


def solution_1600():
    # data_struct.py#ThroneInheritance
    ...


def solution_1702(binary: str) -> str:
    idx = 0
    for i, c in enumerate(binary):
        if c == '0':
            idx = i
            break
    cnt = Counter[str](binary[idx:])
    if cnt['0'] <= 0:
        return binary
    ans = ['1'] * len(binary)
    ans[idx + cnt['0'] - 1] = '0'
    return "".join(ans)


def solution_1702_2(binary: str) -> str:
    i = binary.find('0')
    if i < 0:  # binary 全是 '1'
        return binary
    cnt1 = binary.count('1', i)  # 统计 binary[i:] 中 '1' 的个数
    return '1' * (len(binary) - 1 - cnt1) + '0' + '1' * cnt1


def solution_1766(nums: List[int], edges: List[List[int]]) -> List[int]:
    # 可预处理
    MX = 51
    coprime = [[j for j in range(1, MX) if gcd(i, j) == 1] for i in range(MX)]
    n = len(nums)
    g = [[] for _ in range(n)]
    for i, j in edges:
        g[i].append(j)
        g[j].append(i)

    ans = [0] * n
    val_depth_id = [(-1, -1)] * MX

    def dfs(x, fa, depth):
        val = nums[x]
        # 计算与 val 互质的祖先节点值中，节点深度最大的节点编号
        ans[x] = max(val_depth_id[j] for j in coprime[val])[1]
        tmp = val_depth_id[val]
        val_depth_id[val] = (depth, x)
        for y in g[x]:
            if y != fa:
                dfs(y, x, depth + 1)
        val_depth_id[val] = tmp

    dfs(0, -1, 0)
    return ans


def solution_1883(dist: List[int], speed: int, hoursBefore: int) -> int:
    """
    f[i][j]完成最多跳过i次，完成j条路的时间
    """
    if sum(dist) > speed * hoursBefore:
        return -1
    f = [0] * len(dist)
    for i in count(0):
        pre = 0  # f[i-1][0]
        for j, d in enumerate(dist[:-1]):
            tmp = f[j + 1]
            f[j + 1] = (f[j] + d + speed - 1) // speed * speed  # 不跳过dist[j]的休息
            if i:
                f[j + 1] = min(f[j + 1], pre + d)  # 跳过
            pre = tmp  # f[i-1][j+1]
        if f[-1] + dist[-1] <= speed * hoursBefore:
            return i


def solution_1652(code: List[int], k: int) -> List[int]:
    n = len(code)
    s = [0] * (n + 1)
    for i in range(n):
        s[i + 1] = s[i] + code[i]
    ans = [0] * n
    if k >= 0:
        for i in range(n):
            if i + k < n:
                ans[i] = s[i + k + 1] - s[i + 1]
            else:
                ans[i] = s[n] - s[i + 1] + s[i + k + 1 - n]
    else:
        for i in range(n):
            if i + k < 0:
                ans[i] = s[n] - s[n + k + i] + s[i]
            else:
                ans[i] = s[i] - s[i + k]
    return ans


def solution_1553(n: int) -> int:
    @cache
    def dfs(x: int) -> int:
        if x == 0:
            return 0
        if x == 1:
            return 1
        return min(dfs(x // 2) + x % 2, dfs(x // 3) + x % 3) + 1

    ans = dfs(n)
    dfs.cache_clear()
    return ans


def solution_1953(milestones: List[int]) -> int:
    mx = max(milestones)
    total = sum(milestones)
    if mx * 2 <= total:
        return total
    else:
        return (total - mx) * 2 + 1


def solution_1535(arr: List[int], k: int) -> int:
    n = len(arr)
    if k >= n - 1:
        return max(arr)
    q = deque(arr)
    cnt = 0
    ans = -1
    while cnt < k:
        t1 = q.popleft()
        t2 = q.popleft()
        w = -1
        if t1 > t2:
            q.append(t2)
            w = t1
        elif t2 > t1:
            q.append(t1)
            w = t2
        if w == ans:
            cnt += 1
        else:
            ans = w
            cnt = 1
        q.appendleft(w)
    return ans


def solution_1535_2(arr: List[int], k: int) -> int:
    mx = arr[0]
    win = -1
    for x in arr:
        if x > mx:
            mx = x
            win = 0
        win += 1
        if win == k:
            break
    return mx


def solution_1542(s: str) -> int:
    digits = 10
    n = len(s)
    pos = [n] * (1 << digits)  # n 表示没有找到异或前缀和
    pos[0] = -1
    ans = pre = 0
    for i, x in enumerate(map(int, s)):
        pre ^= 1 << x
        ans = max(ans, i - pos[pre],
                  max(i - pos[pre ^ 1 << d] for d in range(digits)))
        if pos[pre] == n:  # 首次遇到值为pre的前缀异或和，记录下标i
            pos[pre] = i
    return ans


def solution_1673(nums: List[int], k: int) -> List[int]:
    s = [-1]
    n = len(nums)
    for i, x in enumerate(nums):
        while s[-1] > x and len(s) - 2 + n - i >= k:
            s.pop()
        s.append(x)
    return s[1:k + 1]


def solution_1738(matrix: List[List[int]], k: int) -> int:
    m, n = len(matrix), len(matrix[0])
    s = [[0] * (n + 1) for _ in range(m + 1)]
    for i, row in enumerate(matrix):
        for j, val in enumerate(row):
            s[i + 1][j + 1] = s[i + 1][j] ^ s[i][j + 1] ^ s[i][j] ^ val
    return sorted(x for row in s[1:] for x in row[1:])[-k]


def solution_1515(positions: List[List[int]]) -> float:
    eps = 1e-7
    alpha = 1.0
    decay = 1e-3

    n = len(positions)
    batchSize = n

    x = sum(pos[0] for pos in positions) / n
    y = sum(pos[1] for pos in positions) / n

    getDist = lambda xc, yc: sum(((x - xc) ** 2 + (y - yc) ** 2) ** 0.5 for x, y in positions)

    while True:
        random.shuffle(positions)
        xPrev, yPrev = x, y
        for i in range(0, n, batchSize):
            j = min(i + batchSize, n)
            dx, dy = 0.0, 0.0
            for k in range(i, j):
                pos = positions[k]
                dx += (x - pos[0]) / (sqrt((x - pos[0]) * (x - pos[0]) + (y - pos[1]) * (y - pos[1])) + eps)
                dy += (y - pos[1]) / (sqrt((x - pos[0]) * (x - pos[0]) + (y - pos[1]) * (y - pos[1])) + eps)

            x -= alpha * dx
            y -= alpha * dy

            alpha *= (1.0 - decay)

        if ((x - xPrev) ** 2 + (y - yPrev) ** 2) ** 0.5 < eps:
            break
    return getDist(x, y)


def solution_1521(arr: List[int], target: int) -> int:
    ans = inf
    p = set()
    for x in arr:
        c = {x}
        for y in p:
            c.add(x & y)
        for t in c:
            ans = min(ans, abs(target - t))
        p = c
    return ans


def solution_1958(board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
    ds = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]
    m = 8
    n = 8
    for d in ds:
        x, y = rMove, cMove
        tx, ty = x + d[0], y + d[1]
        if tx < 0 or tx >= m or ty < 0 or ty >= n or board[tx][ty] == '.' or board[tx][ty] == color:
            continue
        while True:
            tx += d[0]
            ty += d[1]
            if tx < 0 or tx >= m or ty < 0 or ty >= n or board[tx][ty] == '.':
                break
            if board[tx][ty] == color:
                return True
    return False


def solution_1558(nums: List[int]) -> int:
    m = max(nums).bit_length()
    ans = 0
    for x in nums:
        ans += x.bit_count()
    return ans + m - 1 if ans != 0 else 0


def solution_1712(self, nums: List[int]) -> int:
    MOD = 10 ** 9 + 7
    n = len(nums)
    pre = list(accumulate(nums))
    print(pre)
    ans = 0
    for i in range(n):
        l = max(i + 1, bisect_left(pre, pre[i] + pre[i]))  # 中间段必须满足大于左段
        r = min(n - 1, bisect_right(pre, (pre[i] + pre[-1]) // 2))  # 除去left部分后的中点位置
        ans = ans + max(0, r - l)
    return ans % MOD


def solution_1835(a: List[int], b: List[int]) -> int:
    return reduce(xor, a, 0) & reduce(xor, b, 0)  # a & (b ^ c) = (a & b) ^ (a & c)


def solution_1863(nums: List[int]) -> int:
    ans = 0
    for x in nums:
        ans |= x
    return ans << (len(nums) - 1)


def solution_1803(nums: List[int], low: int, high: int) -> int:
    ans, cnt = 0, Counter[int](nums)  # 从前k位开始统计
    high += 1  # 减少特判
    while high:
        nxt = Counter[int]()
        for x, c in cnt.items():
            if high & 1: ans += c * cnt[x ^ (high - 1)]  # 统计是当第k位为1时，前k-1位与high相同，第k位能与x异或为0的值，也就是前缀相同，但小于high的值
            if low & 1: ans -= c * cnt[x ^ (low - 1)]  # 同上
            nxt[x >> 1] += c  # 记录前k-1位
        cnt = nxt
        low >>= 1
        high >>= 1
    return ans // 2


def solution_1734(encoded: List[int]) -> List[int]:
    n = len(encoded)
    x = 1 if (n // 2 + 1) % 2 else 0
    for i in range(1, n, 2):
        x ^= encoded[i]
    perm = [x]
    for i in range(n):
        perm.append(encoded[i] ^ perm[i])
    return perm


def solution_1765(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    dp = [[-1] * n for _ in range(m)]
    for i, row in enumerate(mat):
        for j, x in enumerate(row):
            if x == 1:
                dp[i][j] = 0
    for i in range(m):
        for j in range(n):
            if dp[i][j] == 0:
                continue
            mn = inf
            if i > 0:
                mn = min(mn, dp[i - 1][j] + 1)
            if j > 0:
                mn = min(mn, dp[i][j - 1] + 1)
            dp[i][j] = mn
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if dp[i][j] == 0:
                continue
            mn = dp[i][j]
            if i < m - 1:
                mn = min(mn, dp[i + 1][j] + 1)
            if j < n - 1:
                mn = min(mn, dp[i][j + 1] + 1)
            dp[i][j] = mn
    return dp


def solution_1673_2(nums: List[int], k: int) -> List[int]:
    s = [-1]
    n = len(nums)
    for i in range(n):
        # if n - i + len(s) == k:
        #     return s + nums[i:]
        x = nums[i]
        while x < s[-1] and n - i + len(s) - 1 > k:
            s.pop()
        s.append(x)
    return s[1:k + 1]


def solution_1829(nums: List[int], maximumBit: int) -> List[int]:
    pre = 0
    ans = [0] * len(nums)
    mx = (1 << maximumBit) - 1
    for i, x in enumerate(nums):
        pre ^= x
        ans[len(nums) - i - 1] = (~pre) & mx
    return ans


def solution_1720(encoded: List[int], first: int) -> List[int]:
    encoded = [first] + encoded
    for i in range(1, len(encoded)):
        encoded[i] = encoded[i] ^ encoded[i - 1]
    return encoded


def solution_1845():
    # data_struct#SeatManager
    ...


def solution_1928(maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
    n = len(passingFees)
    g = [[] for _ in range(n)]
    for x, y, t in edges:
        g[x].append((y, t))
        g[y].append((x, t))

    cost = [inf] * n
    time = [inf] * n
    cost[0] = passingFees[0]
    time[0] = 0

    h = [(cost[0], time[0], 0)]
    while h:
        cost_x, time_x, x = heappop(h)
        if x == n - 1:
            return cost_x
        if cost_x > cost[x] and time_x > time[x]:
            continue
        for y, t in g[x]:
            new_time = time_x + t
            if new_time > maxTime:
                continue
            new_cost = cost_x + passingFees[y]
            if new_cost < cost[y]:
                cost[y] = new_cost
                time[y] = new_time
                heappush(h, (new_cost, new_time, y))
            elif new_time < time[y]:
                time[y] = new_time
                heappush(h, (new_cost, new_time, y))
    return -1


def solution_1870(dist: List[int], hour: float) -> int:
    def check(x):
        cur = 0
        for d in dist[:-1]:
            t, r = divmod(d, x)
            cur += t if not r else t + 1
        return cur + dist[-1] / x <= hour

    lo = 1
    hi = 10 ** 7
    ans = bisect_left(range(lo, hi + 1), True, key=check) + lo
    return ans if ans <= hi else -1


def solution_1547(n: int, cuts: List[int]) -> int:
    cuts.sort()
    cuts = [0] + cuts + [n]
    n = len(cuts)

    dp = [[0] * n for _ in range(n)]

    for i in range(n - 3, -1, -1):  # range(n - 2, -1, -1)
        for j in range(i + 2, n):
            for k in range(i + 1, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
            dp[i][j] = dp[i][j] + cuts[j] - cuts[i]

    return dp[0][n - 1]
